package com.zyk.java8;

/**
 * @author zhangsan
 * @date 2021/5/8 22:20
 */
public class T {

    public static int longestCommonSubStr(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int max = -1;
        for (int i = 0; i < s1.length; i++) {
            for (int j = 0; j < s2.length; j++) {
                max = Math.max(max, process(s1, s2, i, j));
            }
        }
        return max;
    }

    private static int process(char[] s1, char[] s2, int i, int j) {
        if (i == s1.length || j == s2.length)
            return 0;
        if (s1[i] != s2[j])
            return 0;
        return process(s1, s2, i + 1, j + 1) + 1;
    }

    public static int longestCommonSubsequence2(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        return process2(s1, s2, 0, 0);
    }

    private static int process2(char[] s1, char[] s2, int i, int j) {
        boolean isEqual = s1[i] == s2[j];
        int v = s1[i] == s2[j] ? 1 : 0;
        if (i == s1.length - 1 && j == s2.length - 1) {
            return isEqual ? 1 : 0;     // 匹配上了, 就要停因为使用过了,不能再用了
        } else if (i == s1.length - 1)
            return isEqual ? 1 : 0;
        else if (j == s2.length - 1) {
            return isEqual ? 1 : 0;
        } else {
            // 如果还想用这个做匹配, 就不能把当前i 和当前j 做匹配的结果用上
            int p2 = process2(s1, s2, i, j + 1);
            int p3 = process2(s1, s2, i + 1, j);
            int p1 = process2(s1, s2, i + 1, j + 1) + v;
            return Math.max(p1, Math.max(p2, p3));
        }
    }

    public static int dp(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int N = s1.length;
        int M = s2.length;
        int[][] dp = new int[N][M];
        dp[0][0] = s1[0] == s2[0] ? 1 : 0;
        for (int i = 1; i < N; i++) {
            dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0];
        }
        for (int j = 1; j < M; j++) {
            dp[0][j] = s1[0] == s2[j] ? 1 : dp[0][j - 1];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i][j] = Math.max((dp[i][j - 1]), Math.max((dp[i - 1][j]), (s1[i] == s2[j] ? 1 + dp[i - 1][j - 1] : 0)));
            }
        }
        return dp[N - 1][M - 1];
    }


    public static void main(String[] args) {
        String s1 = "cBBb";
        String s2 = "eEEB";
//        System.out.println(longestCommonSubStr(s1, s2));
//        System.out.println(longestCommonSubsequence(s1, s2));
//        System.out.println(dp(s1, s2));
        System.out.println(dp(s1, s2));
        System.out.println(longestCommonSubsequence2(s1, s2));

        /*int times = 100000;
        int maxLen = 5;
        for (int i = 0; i < times; i++) {
            String str1 = generateRandomString(5);
            String str2 = generateRandomString(5);
            int ans2 = dp(str1, str2);
            int ans1 = longestCommonSubsequence2(str1, str2);
            if(ans1 != ans2) {
                System.out.println(str1);
                System.out.println(str2);
                System.out.println(ans1);
                System.out.println(ans2);
                break;
            }
        }*/
    }

    private static String generateRandomString(int maxStringLength) {
        char[] ans = new char[(int) ((maxStringLength) * Math.random()) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 5);
            ans[i] = (Math.random() < 0.5) ? (char) ((65) + value) : (char) (97 + value);
        }
        return new String(ans);
    }

}
